//
// Created by PC on 2017/12/26.
//

#ifndef DFSANDCOMPONENTS_OULAPATH_H
#define DFSANDCOMPONENTS_OULAPATH_H
#include <iostream>
#include <vector>
#include <cassert>
#include <stack>

using  namespace std;

template <typename Graph>
class OulaPath{
private:
    Graph &G;
    int s;
    int *from;
    vector<Edge> edge;
    void dfs(int s){
        typename Graph::adjIterator adj(G,s);
        for (int w = adj.begin(); !adj.end(); w = adj.next()){
            if(s!=w) {
                if(!edge[w].visited)
                for (int i = 0; i < edge.size(); i++) {
                    if ((edge[i].b == s || w) && (edge[i].e == s || w)) {
                        edge[i].visited = true;
                        from[w] = s;
                        dfs(w);
                    }
                }
                else
                    return;
            }
            else
            {
                if(edge.size()==G.E())
                    break;
                else
                    return;
            }
        }
    }

public:
    OulaPath(Graph graph,int s):G(graph){
        assert(s>=0 && s<graph.V());
        this->s=s;
        this->from=new int[graph.V()];
        edge=vector<Edge>();
        for (int k = 0; k < graph.V(); k++) {
            from[k]=-1;
            for (int i = 0; i < graph.V(); i++)
                edge.push_back(Edge(k,i,false));
        }
        dfs(s);
    }
    ~OulaPath(){
        delete[] edge;
    }
    void path(){
        vector<int> vec;
        stack<int> stack1;

        int p=s;
        while (p != -1) {
            stack1.push(p);
            p=from[p];
        }
        vec.clear();
        while (!stack1.empty()) {
            vec.push_back(stack1.top());
            stack1.pop();
        }
        for (int i = 0; i < vec.size(); i++) {
            cout<<vec[i];
            if(i<vec.size()-1)
                cout<<" -> ";
            else
                cout<<endl;
        }
    }
    class Edge{
    public:
        int b=0,e=0;
        bool visited;
        Edge(int b, int e, bool visited) : b(b), e(e), visited(visited) {}
        ~Edge(){}
    };

};

#endif //DFSANDCOMPONENTS_OULAPATH_H
